package 我的Java学习_算法基础.day_08;

/**
 * @author 挚爱之夕
 * @date 2021/8/24 - 08 - 24 - 15:48
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _131_记忆型递归的优势_斐波那契数列 {
    public static void main(String[] args) {
        int n = 50;
        memory = new long[n+1];
        long now = System.currentTimeMillis();
        long answer1 = f1(n);
        System.out.println(answer1+" 耗时： "+(System.currentTimeMillis()-now)+" ms");
        now = System.currentTimeMillis();
        long answer = f(n);
        System.out.println(answer+" 耗时： "+(System.currentTimeMillis()-now)+" ms");
    }
    private static long f(int n){
        if(n==1||n==2)
            return 1;
        return f(n-1)+f(n-2);
    }
    static long[] memory;
    private static long f1(int n){
        if(n==1||n==2)
            return 1;
        if(memory[n]>0)
            return memory[n];
        long a1 = f1(n-1);
        long a2 = f1(n-2);
        memory[n] = a1+a2;
        return a1+a2;
    }
}
